# 汉明距离总和：https://leetcode-cn.com/problems/total-hamming-distance/

# 暴力解法
class Solution:
    def totalHammingDistance(self, nums) -> int:
        count = 0
        for i in range(len(nums)):
            for j in range(i, len(nums)):
                temp = nums[i] ^ nums[j]
                while temp != 0:
                    temp &= temp - 1
                    count += 1
        return count
        

# 优化解法
class Solution:
    def totalHammingDistance(self, nums) -> int:
        """
            算法： 计算每一位对应的 1的个数，
            原理： 因为只有1和0， 而且不同才能产生1个汉明距离。 那么加入 nums有五个元素。 在最低位 一共有  3 个1， 2个是0. 那么 一个0 可以和 3个产生3个汉明位。
            那么就算一位上的汉明位计算公式就是： 汉明个数 = 1的个数 乘 0的个数

            根据题目要求：0 <= nums[i] <= 10^9  说明 数字是一个int类型， 小于32位
        """
        # 计算每一位的1个数和
        count = [0]*32
        n = len(nums)
        rst = 0
        for i in range(32):
            # 计算当前位的 1数量
            for num in nums:
                if num & (1 << i): count[i] += 1

            # 计算当前位的汉明距离总和
            rst += (n-count[i]) * count[i]

        return rst